package Ep07_BackTrack.Back7_0039;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jimmy Zhan WORKSTATION
 * @since 2023/7/12 10:19
 * 说明：0039 组合总和
 *           这种方法是暴力搜索，因为有些叶子结点是不需要搜索的
 *           可以剪枝
 */

public class Mine {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        traversal(candidates, target, 0);
        return res;
    }

    private void traversal(int[] candidates, int target, int start) {
        // 终止条件
        if (sum == target) {
            res.add(new ArrayList<Integer>(path));
            return;
        } else if (sum > target) {
            return;
        }

        // 递归逻辑
        for (int i = start; i < candidates.length; ++i) {
            sum += candidates[i];
            path.add(candidates[i]);
            traversal(candidates, target, start);
            path.remove(path.size() - 1);
            sum -= candidates[i];
            start++;
        }
    }
}
